package greedy;

/**
 * 134. 加油站
 * <p>
 * 在一条环路上有 n个加油站，其中第 i个加油站有汽油gas[i]升。
 * <p>
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。
 * <p>
 * 给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
 */
public class N134_GasStation {
    public int canCompleteCircuit_Greedy2(int[] gas, int[] cost) {
        int start = 0;      // 开始位置
        int curSum = 0;     // 局部油剩余量
        int totalSum = 0;   // 全局油剩余量
        for (int i = 0; i < cost.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {   // 如果局部油剩余量小于0
                curSum = 0;
                start = i + 1;
            }
        }
        return totalSum < 0 ? -1 : start;
    }


    // 贪心思路 1 （实际上看不出贪心思想。。。。。。。。）
    public int canCompleteCircuit_Greedy1(int[] gas, int[] cost) {
        int curSum = 0;     // 累计剩余油量
        int min = Integer.MAX_VALUE;    // 累计油量最低的时候
        for (int i = 0; i < cost.length; i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            min = Math.min(curSum, min);
        }
        if (curSum < 0) return -1;  // 总油耗大于总油量，肯定是不能走一圈的 -1
        if (min >= 0) return 0;     // 走完一圈之后，油量没有低过0，走一圈，起点是0
        //  如果min是负数，就说明不是从0出发的，从后往前，能把 min 填成非负数就说明可以走一圈（具体不太清楚）
        for (int i = cost.length - 1; i >= 0; i--) {
            min += gas[i] - cost[i];
            if (min >= 0) return i;
        }
        return -1;
    }

    // 暴力法，力扣上过不了。。。
    public int canCompleteCircuit_violence(int[] gas, int[] cost) {
        for (int i = 0; i < cost.length; i++) {
            int g = gas[i] - cost[i];
            int index = (i + 1) % cost.length;
            while (g > 0 && index != i) {
                g += gas[index] - cost[index];
                index = (index + 1) % cost.length;
            }
            if (g >= 0 && index == i) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        N134_GasStation solution = new N134_GasStation();
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        System.out.println(solution.canCompleteCircuit_Greedy2(gas, cost));
    }
}
